题解：B3958 [GESP202403 四级] 相似字符串

封面

思路：

因为只有通过删除一个字符，或插入一个字符，或修改一个字符变成另一个字符串才是相似的，所以我们可以分成五种情况。

第一种情况，如果第一个字符串和第二个字符串是相同的，那么这两个字符串是相似的，代码如下。

if(a==b){// 特判如果 a 与 b 相同的情况 
	cout<<"similar\n";continue;
}

第二种情况，如果第一个字符串的长度等于第二个字符串的长度且两个字符串不相同，如果它们是相似的，那么只能是修改一个字符出来的，两个字符串之间至少有第一个字符串的长度减一个字符是相同的，且位置相同，代码如下。

if(a.size()==b.size()){// a 的长度与 b 的长度相同
	for(int i=0;i<a.size();i++){
		if(a[i]==b[i])cnt++;// 都用 i 因为要在同一个位置 
	}
	if(cnt+1==a.size()||cnt==a.size()){// 至少有 a.size()-1 个字符相同且在同一个位置 
		cout<<"similar\n";
	}
	else cout<<"not similar\n";
}

第三种情况第一个字符串的长度比第二个字符串的长度小一，如果它们是相似的，那么只能是通过插入一个字符出来的，这下不用是同一个位置了，但是顺序要一样，所以我们可以定义一个变量 cccc 用来储存现在历遍到了第一个字符串的第几个字符，第二个字符串用循环历遍，代码如下。

else if(a.size()+1==b.size()){//a 的长度加一等于 b 的长度 
	for(int i=0;i<b.size();i++){
		if(a[cc]==b[i])cnt++,cc++;
	}
	if(cnt==a.size()){// 因为是插入的所以相同的要有 a 的长度个，也就是去掉那个插入的字符后要完全相同 
		cout<<"similar\n";
	}
	else cout<<"not similar\n";
}

第四种情况第一个字符串的长度比第二个字符串的长度大一，如果它们是相似的，那么只能是通过删除一个字符出来的，因为它们是相似的所以可以看做第一个字符串是第二个字符串通过插入操作得到的，只需要交换两个字符串然后和第三种情况一样写就可以了，代码如下。

else if(a.size()-1==b.size()){// a 的长度减一等于 b 的长度 
	swap(a,b);// 交换 a 和 b
	for(int i=0;i<b.size();i++){
		if(a[cc]==b[i])cnt++,cc++;
	}
	if(cnt==a.size()){
		cout<<"similar\n";
	}
	else cout<<"not similar\n";
}

第五种情况，以上情况都不是也就是说肯定不是通过删除一个字符，或插入一个字符，或修改一个字符出现的，所以可以直接输出，代码如下。

else{
	cout<<"not similar\n";
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		string a,b;
		cin>>a>>b;
		int cnt=0,cc=0;
		if(a==b){// 1
			cout<<"similar\n";continue;
		}
		if(a.size()==b.size()){// 2
			for(int i=0;i<a.size();i++){
				if(a[i]==b[i])cnt++;
			}
			if(cnt+1==a.size()||cnt==a.size()){
				cout<<"similar\n";
			}
			else cout<<"not similar\n";
		}
		else if(a.size()+1==b.size()){// 3
			for(int i=0;i<b.size();i++){
				if(a[cc]==b[i])cnt++,cc++;
			}
			if(cnt==a.size()){
				cout<<"similar\n";
			}
			else cout<<"not similar\n";
		}
		else if(a.size()-1==b.size()){
			swap(a,b);
			for(int i=0;i<b.size();i++){
				if(a[cc]==b[i])cnt++,cc++;
			}
			if(cnt==a.size()){
				cout<<"similar\n";
			}
			else cout<<"not similar\n";
		}
		else{
			cout<<"not similar\n";
		}
	} 
	return 0;
}